#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: fake_coins.py 
@version:
@time: 2024/01/18

找出众多金币中的假币，最简单粗暴的方式就是将金币一个一个地随机取出进行称重，直到找到其中的假币为止，这样做时间复杂度为O(n)。

在金币数量巨大的情况下，这是一种十分低效的做法，因此考虑不断缩小问题规律，采用分治算法来解决这一问题。

将整体一分为二，比较这两者的重量，假币一定存在于重量较小的那部分里，因此可以只对重量较小的那一部分按照同样办法再做分割，如此一来就将问题规模从n缩小到n/2，大大降低了
时间成本，当n的数量巨大时，这种优化的效果就更加明显了。

1. coins变量：表示给定的n个金币的重量。
2. low变量：表示当前判断的第一个金币的位置。
3. high变量：表示当前判断的最后一个金币的位置。
4. mid变量：表示当前判断的金币的中间位置。
5. sum1变量：表示从第一个金币到中间金币的重量之和
6. sum2变量：表示从中间金币到最后一个金币的重量之和
7. re变量：表示假币所在位置。

当金币数量为n时，由于下标从0开始，因此low为0，high为n-1。sum1、sum2的初始值为0，而re的初始值为-1，当袋子中存在假币时，更新re值；当袋子中不存在假币时，则返回-1.

sum1 = sum2 = 0
re=-1

输入的low和high主要分为4种情况

1. 当low=high时，说明假币就在此处，将low值返回即可

if low == high:
    return high

2. 当low+1=high时，说明此时仅有两枚金币，将其中重量较小者所在位置返回即可

if high-low == 1:
  if coins[high]<coins[low]:
    return high
  else:
    return low

3. 若不满足以上两种情况，则对金币数量进行判断。当金币总数为偶数时，分别计算前半部分和后半部分总重量，从二者中选择重量较小的那一部分，
在调用函数进行判断。

if (high-low+1)%2==0:
  mid=int((high-low+1)/2)
  sum1=sum(coins[low:low+mid])
  sum2=sum(coins[low+mid:high+1])
  if sum1 > sum2:
    re=self.fakecoin(low+mid,high,coins)
    return re
  elif sum1 < sum2:
    re = self.fakecoin(low,low+mid-1,coins)
    return re

4. 当金币数量为奇数时，找到中间的位置，计算中间位置前的所有金币重量和中间位置后的所有金币重量，找重量较小的那一部分金币再调用函数进行判断

elif (high-low+1)%2!=0:
  mid=int((high-low)/2)
  sum1=sum(coins[low:low+mid])
  sum2=sum(coins[low+mid+1:high+1])
  if sum1>sum2:
    re = self.fakecoin(low+mid+1,high,coins)
    return re
  elif sum1<sum2:
    re = self.fakecoin(low,low+mid-1,coins)
    return re

如果二者重量相等，说明中间位置的金币可能是假币，判断中间位置金币重量与low位置金币重量是否相等，如果不等，则说明假币存在于中间位置；如果相等，则说明袋子中无假币。

elif coins[low+mid]!=coins[low]:
  return low+mid
"""
import pdb

coins = [1, 1, 1, 1, 1, 0]


class Solution:
    def fakecoin(self, low, high, coins):
        sum1 = sum2 = 0
        re = -1
        if low == high:
            return high
        if high - low == 1:
            if coins[high] < coins[low]:
                return high
            else:
                return low

        # 1 1 1 1 1 0
        # 0 1 2 3 4 5
        # 偶数
        if (high - low + 1) % 2 == 0:
            mid = int((high - low + 1) / 2)
            sum1 = sum(coins[low:low + mid])
            sum2 = sum(coins[low + mid:high + 1])
            if sum1 > sum2:
                re = self.fakecoin(low + mid, high, coins)
                return re
            elif sum1 < sum2:
                re = self.fakecoin(low, low + mid - 1, coins)
                return re
        # 奇数
        elif (high - low + 1) % 2 != 0:
            mid = int((high - low) / 2)
            sum1 = sum(coins[low:low + mid])
            sum2 = sum(coins[low + mid + 1:high + 1])
            if sum1 > sum2:
                re = self.fakecoin(low + mid, high, coins)
                return re
            elif sum1 < sum2:
                re = self.fakecoin(low, low + mid - 1, coins)
                return re
            elif coins[low + mid] != coins[low]:
                return low + mid
        return re


print(Solution().fakecoin(0, len(coins) - 1, coins))
